package com.agile.leetcode.lfu;


import java.util.*;

/**
 * @Author:ChenZhangKun
 * @Date: 2023/2/19 15:39
 */
public class LFUCache {
    // 维护节点key---包装的node
    private Map<String, Node> nodeMap = new HashMap<>();
    // 维护使用频率，同个频率可以是多个，这里挂载一个链表  ***>这里可以考虑使用优先队列，使用node维护key和time，time为每次放入的时间，这样根据大小堆从顶部取就可以了.+

    private Map<Integer, LinkedHashSet<String>> freqMap = new HashMap<>();
    private int miniFreq = 1;
    private int capacity;

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public void put(String key, String value) {
        // key是否存在
        Node node = nodeMap.get(key);
        if (node != null) {
            // 更新freqMap
            this.refresh(node.freq, key);
            // 频次更细
            node.freq = node.freq + 1;
            //
        } else {
            // 没插入
            // 校验长度
            int size = nodeMap.size();
            if (size >= capacity) {
                // 淘汰
                LinkedHashSet<String> strings = freqMap.get(miniFreq);
                // 这里先取第一个，按理说应该取最先放入那个
                Iterator<String> iterator = strings.iterator();
                String next = iterator.next();
                nodeMap.remove(next);
                // 移除
                iterator.remove();
                // 添加
                Node n=new Node(key,value);
                nodeMap.put(key, n);
                this.refresh(1, key);
            } else {
                Node newNode = new Node(key, value);
                nodeMap.put(key, newNode);
                this.refresh(1, key);
            }
        }
    }

    public String get(String key) {
        Node node = nodeMap.get(key);
        if (node!=null){
            node.freq = node.freq + 1;
            // 更新frequency
            refresh(node.freq, key);
            return node.value;
        }
      return null;
    }

    private void refresh(int freq, String key) {
        if (freq==1){
            LinkedHashSet<String> linkedHashSet = freqMap.get(1);
            if (null==linkedHashSet){
                 linkedHashSet=new LinkedHashSet<>();
            }
            linkedHashSet.add(key);
            freqMap.put(1,linkedHashSet);
            return;
        }
        LinkedHashSet<String> linkedHashSet = freqMap.get(freq-1);
        // 移除
        linkedHashSet.remove(key);
        // 新增
        LinkedHashSet<String> strings = freqMap.get(freq );
        if (strings == null){
            strings=new LinkedHashSet<>();
        }
        strings.add(key);
        freqMap.put(freq, strings);

        Set<Integer> set = freqMap.keySet();
        for (Integer integer : set) {
            if (freqMap.get(integer) != null) {
                miniFreq = integer;
                break;
            }
        }
    }

    public static void main(String[] args) {
        LFUCache lfuCache=new LFUCache(3);
        lfuCache.put("a","a");
        lfuCache.put("b","b");
        lfuCache.put("c","c");
        System.out.println(lfuCache.get("b"));
        System.out.println(lfuCache.get("a"));
        lfuCache.put("d","d");
        System.out.println(lfuCache.get("c"));
    }


}

class Node {
    String key;
    String value;
    int freq = 1;

    public Node(String key, String value) {
        this.key = key;
        this.value = value;
    }
}
